package codingforgreat.lchot150;

public class Lc010 {
    public static boolean isMatch(String str, String pat) {
        char[] s = str.toCharArray();
        char[] p = pat.toCharArray();
        return process(s,p,0,0);
    }
    public static boolean process(char[] s, char[] p, int i, int j) {
        if (i == s.length) {
            if (j == p.length) {
                return true;
            } else {
                return ((j + 1) < p.length) && (p[j + 1] == '*') && process(s, p, i, j + 2);
            }
        } else {//s还有 p没了
            if (j == p.length) {
                return false;
            } else {
                if (j + 1 == p.length || p[j + 1] != '*') {
                    return (s[i] == p[j] || p[j] == '.') && process(s, p, i + 1, j + 1);
                } else {//j没到头且 j + 1 = *
                    boolean p1 = process(s, p, i, j + 2);
                    boolean p2 = process(s, p, i + 1, j) && (s[i] == p[j] || p[j] == '.');
                    return p1 || p2;

                }
            }
        }
    }
}
